package org.lql.algo.codecrush.week006;

/**
 * @author: liangqinglong
 * @date: 2025-08-07 17:48
 * @description: LCR 139. 训练计划 I <a href="https://leetcode.cn/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof/description/">...</a>
 **/
public class TrainingPlan {

	/**
	 * 教练使用整数数组 actions 记录一系列核心肌群训练项目编号。
	 * 为增强训练趣味性，需要将所有奇数编号训练项目调整至偶数编号训练项目之前。
	 * 请将调整后的训练项目编号以 数组 形式返回。
	 * <p>
	 * <p>
	 * <p>
	 * 示例 1：
	 * <p>
	 * 输入：actions = [1,2,3,4,5]
	 * 输出：[1,3,5,2,4]
	 * 解释：为正确答案之一
	 * <p>
	 * <p>
	 * 提示：
	 * <p>
	 * 0 <= actions.length <= 50000
	 * 0 <= actions[i] <= 10000
	 */
	// 双指针（原地交换，顺序不保证稳定）
	public int[] trainingPlan(int[] actions) {
		int left = 0, right = actions.length - 1;

		while (left < right) {
			// 左边找偶数
			while (left < right && actions[left] % 2 == 1) {
				left++;
			}
			// 右边找奇数
			while (left < right && actions[right] % 2 == 0) {
				right--;
			}
			// 交换
			if (left < right) {
				int temp = actions[left];
				actions[left] = actions[right];
				actions[right] = temp;
			}
		}
		return actions;
	}

	// 新数组（保持相对顺序，稳定排序）
	public int[] trainingPlanNew(int[] actions) {
		int[] res = new int[actions.length];
		int idx = 0;

		// 先放奇数
		for (int num : actions) {
			if (num % 2 == 1) {
				res[idx++] = num;
			}
		}
		// 再放偶数
		for (int num : actions) {
			if (num % 2 == 0) {
				res[idx++] = num;
			}
		}
		return res;
	}

	public static void main(String[] args) {
		TrainingPlan trainingPlan = new TrainingPlan();
		int[] actions = {1, 2, 3, 4, 5};
		int[] res = trainingPlan.trainingPlanNew(actions);
		for (int i : res) {
			System.out.print(i + " ");
		}
	}
}
